/*
 * Search in Rotated Sorted Array
Suppose a sorted array is rotated at some pivot unknown to you beforehand.

(i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).

You are given a target value to search. If found in the array return its index, otherwise return -1.

You may assume no duplicate exists in the array.
 */
package com.xinpan.exercise;

public class SearchinRotatedSortedArray {
    public int search(int[] A, int target) {
        // Start typing your Java solution below
        // DO NOT write main() function
        int l = A.length;
        if(l == 0)
            return -1;

        
        int s = 0;
        int e = l-1;
        int m = e;
        while(s <= e)
        {
            m = (s+e)/2;
            if(A[s] < A[m])
                s = m;
            else if(A[s] > A[m])
                e = m;
            else
            {
                if(A[m] < A[l-1])
                    m++;
                break;
            }
        }
        
        
        if(A[m] < target)
            return -1;
            
        if(A[0] > target)
        {
            s = m+1;
            e = l-1;
        }
        else
        {
            s = 0;
            e = m;
        }
        m = -1;
        while(s <= e)
        {
            m = (s+e)/2;
            if(A[m] > target)
                e = m-1;
            else if(A[m] < target)
                s = m+1;
            else
                break;
        }
        
        if(m >= 0 && A[m] == target)
            return m;
        else
            return -1;
        
    }
    
    public static void main(String[] args)
    {
    	SearchinRotatedSortedArray sa = new SearchinRotatedSortedArray();
    	int[] a = {3,5,1};
    	sa.search(a, 1);
    }
}
